:- module(ic_global).
:- export atmost / 3.
:- export sumlist / 2.
:- export sum_ge_zero / 1.
:- export sorted / 3.
:- export sorted / 2.
:- export maxlist / 2.
:- export minlist / 2.
:- export lexico_le / 2.
:- export ordered_sum / 2.
:- export ordered / 2.
:- export occurrences / 3.
:- export alldifferent / 2.
:- export alldifferent / 1.
:- reexport element / 3 from ic.
:- comment(summary, "Various global constraints over lists of IC variables").
:- comment(author, "J.Schimpf, V.Liatsos, S.Novello, M.Wallace, A.Sadler, IC-Parc").
:- comment(copyright, "Parc Technologies Ltd").
:- comment(date, "$Date: 2003/11/25 16:04:31 $").
:- comment(alldifferent / 1, [template : "alldifferent(+List)", summary : "All members of List are different", desc : html("    All members of List are different.  This is an implementation with\n    the same semantics but with stronger propagation behaviour.\n    It checks for exhaustion of all sub-ranges of possible values.\n    </P><P>\n    Any input variables which do not already have finite bounds will\n    be given default bounds of -10000000 to 10000000.</P>"), eg : "\n    ?- length(Xs,5), Xs::1..4, alldifferent(Xs).\n    no (more) solution.\n\n\n    ?- [X1,X2]::1..2, [X3,X4,X5]::1..5, alldifferent([X1,X2,X3,X4,X5]).\n\n    X1 = X1{[1, 2]}\n    X2 = X2{[1, 2]}\n    X3 = X3{[3..5]}\n    X4 = X4{[3..5]}\n    X5 = X5{[3..5]}\n\n    Delayed goals:\n        alldifferent([X1{[1, 2]}, X2{[1, 2]}], 1)\n        alldifferent([X3{[3..5]}, X4{[3..5]}, X5{[3..5]}], 1)\n    ", see_also : [alldifferent / 1, alldifferent / 2]]).
:- comment(alldifferent / 2, [template : "alldifferent(+List,++Capacity)", summary : "The list List contains at most Capacity elements of each value", desc : html("    This is a generalization of alldifferent/1. It allows repeated\n    elements in the list, but there can be no more than Capacity elements with\n    a particular value.\n    </P><P>\n    Any input variables which do not already have finite bounds will\n    be given default bounds of -10000000 to 10000000.</P>"), see_also : [alldifferent / 1]]).
:- comment(atmost / 3, [summary : "At most N elements of the list List have the value V.\n\n", template : "atmost(+N, ?List, +V)", desc : html("   If List is a list of domain variables and/or integers, this constraint\n   takes care that at most N element of this list have the value V. As soon\n   as some domain variable from the list is updated, this constraint is\n   woken and it checks if the constraint is still satisfiable and if so, if\n   it is already satisfied or not.\n\n<P>\n"), args : ["+N" : "An integer", "?List" : "A list of domain variables or integers", "+V" : "An integer"], resat : "   No.", fail_if : "   Fails if more than N elements of List are instantiated to V.\n\n", see_also : [element / 3]]).
:- comment(element / 3, [summary : "Value is the Index'th element of the integer list List.", template : "element(?Index, ++List, ?Value)", args : ["?Index" : "A variable or an integer.", "++List" : "A non-empty list of integers.", "?Value" : "A variable or an integer."], resat : "No.", fail_if : "Fails if Value is not the Index'th element of List.", desc : html("Deprecated (should never have been included in this module: it's not a\n   global constraint).  Use ic:element/3 instead.\n"), see_also : [ic : element / 3]]).
:- comment(lexico_le / 2, [summary : "List1 is lexicographically less or equal to List2", amode : lexico_le(+, +), args : ["List1" : "List of integers or domain variables", "List2" : "List of integers or domain variables"], desc : html("    \tImposes a lexicographic ordering between the two lists. \n\tI.e.  either is the first element of List1 strictly smaller\n\tthan the first element of List2, or the first elements are\n\tequal and the lexicographic order holds between the two list\n\ttails."), see_also : [ordered / 2], eg : "    L=[X, Y, Z], L :: 0..9, lexico_le(L, [2, 3, 1]).\t\t% X::0..2\n    L=[X, Y, Z], L :: 0..9, lexico_le(L, [2, 3, 1]), X=2.\t% Y::0..3\n    L=[X, Y, Z], L :: 0..9, lexico_le(L, [2, 3, 1]), X#>2.\t% fail\n    L=[X, Y, Z], L :: 0..9, lexico_le(L, [2, 3, 1]), X#<2.\t% true\n    L=[X, Y, Z], L :: 0..9, lexico_le(L, [2, 3, 1]), Y=3.\t% X::0..2\n    L=[X, Y, Z], L :: 0..9, lexico_le(L, [2, 3, 1]), Y#>3.\t% X::0..1\n    L=[X, Y, Z], L :: 0..9, lexico_le(L, [2, 3, 1]), Y#<3.\t% X::0..2\n    lexico_le([2, 3, 1], [3]).\t\t\t\t\t% true\n    "]).
:- comment(maxlist / 2, [summary : "Max is the maximum of the values in List", amode : maxlist(+, ?), args : ["List" : "List of integers or domain variables", "Max" : "Variable or integer"], desc : html("\tMax is the maximum of the values in List.  Operationally: \n\tMax gets updated to reflect the current range of the maximum\n\tof variables and values in List.  Likewise, the list\n\telements get constrained to the maximum given."), see_also : [minlist / 2, sumlist / 2]]).
:- comment(minlist / 2, [summary : "Min is the minimum of the values in List", amode : minlist(+, ?), args : ["List" : "List of integers or domain variables", "Min" : "Variable or integer"], desc : html("    \tMin is the minimum of the values in List.  Operationally: \n\tMin gets updated to reflect the current range of the minimum\n\tof variables and values in List.  Likewise, the list\n\telements get constrained to the minimum given"), see_also : [maxlist / 2, sumlist / 2]]).
:- comment(occurrences / 3, [summary : "The value Value occurs in List N times", amode : occurrences(++, +, ?), args : ["Value" : "Atomic term", "List" : "List of atomic terms or domain variables", "N" : "Variable or integer"], desc : html("    \t  The value Value occurs in List N times.  Operationally:  N\n\t  gets updated to reflect the number of possible occurrences\n\t  in the List.  List elements may get instantiated to Value,\n\t  or Value may be removed from their domain if required by N."), see_also : [element / 3]]).
:- comment(ordered / 2, [summary : "Constrains List to be ordered according to Relation", amode : ordered(++, +), args : ["Relation" : "One of the atoms <, =<, >, >=, =", "List" : "List of integers or domain variables"], see_also : [lexico_le / 2, ordered_sum / 2, sorted / 2]]).
:- comment(ordered_sum / 2, [summary : "The list elements are ordered and their sum is Sum", amode : ordered_sum(+, ?), args : ["List" : "List of integers or domain variables", "Sum" : "Variable or integer"], desc : html("    This constraint is declaratively equivalent to:\n<PRE>\n\tordered_sum(List, Sum) :-\n\t    ordered(=<, List),\n\t    sum(List) #= Sum.\n</PRE>\n    However, additional propagation is performed.\n    </P><P>\n    Any input variables which do not already have finite bounds will\n    be given default bounds of -10000000 to 10000000.</P>"), see_also : [ordered / 2, sumlist / 2]]).
:- comment(sorted / 2, [summary : "Sorted is a sorted permutation of List", amode : sorted(+, +), amode : sorted(+, -), amode : sorted(-, +), args : ["List" : "List of domain variables or integers", "Sorted" : "List of domain variables or integers"], desc : html("    Declaratively: The two lists have the same length and Sorted is a\n    sorted permutation of List.\n<P>\n    Operationally:  the elements in both lists are constrained such\n    that their domains are consistent with the assumption that the\n    list Sorted is the sorted version of the list List.\n<P>\n    One of the two arguments can be uninstantiated or partial lists\n    at call time.\n<P>\n    Any input variables which do not already have finite bounds will\n    be given default bounds of -10000000 to 10000000.\n    "), eg : "\n    ?- length(Xs,4), Xs::0..100, sorted(Xs,Ys), Xs = [8,20|_].\n\n    Xs = [8, 20, _340{[0..100]}, _353{[0..100]}]\n    Ys = [_431{[0..8]}, _413{[0..20]}, _523{[8..100]}, _621{[20..100]}]\n\n\n    ?- length(Ys,4), Ys::0..100, sorted(Xs,Ys), Ys = [8,20|_].\n\n    Xs = [_464{[8..100]}, _477{[8..100]}, _490{[8..100]}, _503{[8..100]}]\n    Ys = [8, 20, _340{[20..100]}, _353{[20..100]}]\n    ", see_also : [sorted / 3, ordered / 2]]).
:- comment(sorted / 3, [summary : "Sorted is a sorted permutation (described by Positions) of List", amode : sorted(+, ?, ?), amode : sorted(?, +, ?), amode : sorted(?, ?, +), args : ["List" : "List of domain variables or integers", "Sorted" : "List of domain variables or integers", "Positions" : "List of domain variables or integers"], desc : html("    Declaratively:  Sorted is a sorted permutation of List.  Positions\n    is a list whose elements range from 1 to N (where N is the length\n    of the lists) indicating the position of each unsorted list\n    element within the sorted list.  The positions are all different. \n    The three lists are constrained to have the same length.\n<P>\n    Operationally:  the elements in all three lists are constrained\n    such that their domains are consistent with the declarative\n    meaning.\n<P>\n    Two of the three arguments can be uninstantiated or partial lists\n    at call time.\n<P>\n    Any input variables which do not already have finite bounds will\n    be given default bounds of -10000000 to 10000000.\n    "), eg : "\n    ?- length(Xs,4), Xs::0..100, sorted(Xs,Ys,Ps), Xs = [8,20|_].\n\n    Xs = [8, 20, _346{[0..100]}, _359{[0..100]}]\n    Ys = [_445{[0..8]}, _427{[0..20]}, _537{[8..100]}, _635{[20..100]}]\n    Ps = [_882{[1..3]}, _895{[2..4]}, _908{[1..4]}, _921{[1..4]}]\n    ", see_also : [sorted / 2, ordered / 2]]).
:- comment(sumlist / 2, [summary : "The sum of the list elements is Sum", amode : sumlist(+, ?), args : ["List" : "List of integers or domain variables", "Sum" : "Variable or integer"], desc : html("<P>    \t  The sum of the list elements is Sum.  This constraint is\n\t  more efficient than the general arithmetic constraint if\n\t  the list is long and Sum is not constrained frequently.\n\t  </P><P>\n\t  Any input variables which do not already have finite bounds will\n\t  be given default bounds of -10000000 to 10000000.</P>"), see_also : [ordered / 2, ordered_sum / 2, (#=) / 2]]).
